The present invention relates to network switching communication protocols generally and to prevention of head of line blocking in particular.
A network switch creates a network among a plurality of end nodes, such as workstations, and other network switches connected thereto. Each end node is connected to one port of the network. The ports also serve to connect network switches together.
Each end node sends packets of data to the network switch which the switch then routes either to another of the end nodes connected thereto or to a network switch to which the destination end node is connected. In the latter case, the receiving network switch routes the packet to the destination end node.
Each network switch has to temporarily store the packets of data which it receives from the units (end node or network switch) connected to it while the switch determines how, when and through which port to retransmit the packets. Each packet can be transmitted to only one destination address (a xe2x80x9cunicastxe2x80x9d packet) or to more than one unit (a xe2x80x9cmulticastxe2x80x9d or xe2x80x9cbroadcastxe2x80x9d packet). For multicast and broadcast packets, the switch typically stores the packet only once and transmits multiple copies of the packet to some (multicast) or all (broadcast) of its ports. Once the packet has been transmitted to all of its destinations, it can be removed from the memory or written over.
Reference is now made to FIG. 1 which schematically illustrates a portion of the data packet transfer process that takes place within the operations of a network switch 10. Switch 10 comprises a central queuing manager 12, an output buffer 14, and a multiplicity of output ports 16. Switch 10 receives incoming data 18 which it stores until transmission as queued data 24 in output buffer 14. At the appropriate time, which is generally when the relevant output port 16 in available, switch 10 transfers the queued data 24 out of the relevant output port 16 as outgoing data 26.
Output buffer 14 is either a pooled buffer which services the entire switch 10 or a plurality of dedicated queues within buffer 14, one queue per output port 16. The exemplary switch 10 shown in FIG. 1 comprises a pooled output buffer 14 and two output ports 16B and 16C.
Incoming data 18 comprises data packets 30, 32, 34 arid 36, which are designated for various destination ports 16. Data 18 is received by manager 12, which identifies the appropriate destination port 16 of the packets 30, 32, 34, and 36 respectively, and dispatches them to the output buffer 14. As an example unicast data packets 32 and 36 are designated for port 16C, unicast data packet 30 is designated for port 16B and multicast packet 34 is designated for both ports 16B and 16C. Output buffer 14 stores the queued data 24 until the relevant port 16 is available, at which point, the outgoing data 26 is transferred to the relevant port 16.
Occasionally, one of the output ports 16 transfers at a faster pace than the other ports or, alternatively, receives more data then the other ports. For whatever reason, a condition may arise where the data 24 for one of the output ports 16 backs up in the output buffer 14 creating a condition where output buffer 14 is unable to receive more data. Manager 12 is aware of the backup in the output buffer 14, typically through a fullness sensor (not shown) measuring the fullness of output buffer 14, and, accordingly, stops receiving incoming data 18 to switch 10.
All incoming data 18 not received by switch 10 is discarded, regardless of its destination output port 16. Not only is the incoming data 18 destined for the full output port discarded but the incoming data 18 destined for the available ports are also discarded. This problem is known as xe2x80x9cHead of Line Blockingxe2x80x9d.
Although switch 10 no longer receives incoming data 18, it continues to send outgoing data 26, and thus, clears out the output buffer 14. Once enough outgoing data 26 has been sent, output buffer 14 empties out and is again able to receive more data 24. Manager 12 reopens inflow of data 18 to switch 10.
For example, if port 16B is backed up, then the output buffer 14 will become full with queued data 24B, while output port 16C will still available to transmit. Manager 12 halts the incoming flow of data 18. All data 18 incoming into switch 12 is halted and discarded, including unicast data packets 32 and 36 and multicast data packet 34 which are designated for the available port 16C.
It is an object of the present invention to prevent Head of Line Blocking as much as possible.
There is therefore provided, in accordance with a preferred embodiment of the present invention, a network switch which includes a plurality of output ports, at least one input port and a queuing manager. Each output port has a control unit associated therewith. The input port receives incoming data destined for various ones of the output ports. The queuing manager directs the incoming data to their destination output ports. Each control unit includes an output queue, a fullness/emptiness sensor and a head of line (HOL) mask. The output queue stores the incoming data destined for its associated output port. The sensor senses when the output queue reaches a fullness or an emptiness state. The HOL mask is connected to the output of the sensor and blocks inflow of the incoming data to the output queue when the sensor senses the fullness state and for enabling inflow when the sensor senses the emptiness state.
There is also provided. In accordance with a preferred embodiment of the present invention, a control unit for an output port of a network switch as described hereinabove.
Finally, there is provided, a method of controlling flow within a network switch, the method comprising the steps of sensing when an output queue of the network switch reaches a fullness or an emptiness state, blocking queueing of incoming data to the output queue when the fullness state is sensed, discarding of unicast packets destined to the full output port queue, avoiding queuing of multicast packets to said output port queue and enabling queueing when the emptiness state is sensed.